【week6】322. Coin Change

322. Coin Change

题目

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

解题报告

题意很简单，就是给定硬币面值，求出能凑出目标数目的最小硬币数目，如果不能，则返回 -1。

显然不能用贪心做，看上去就像是动规的题，所以我刚开始就往上面考虑。虽然这么说，但是在动规时我还是无意间用了贪心的思想，刚开始写的是，dp[i] 表示凑出 i 元需要的最小数目，然后我每次都找出最大的可以用的硬币，求出使得 dp[i - maxAvailable * n] + n 最小的 n，然而无奈 WA。想了想这种算法有极大的 bug，如果 i 不是 maxAvailable 的倍数，那最后答案便是 -1，而且根本无需找那个最小的 n，n 即是 1。

想了很久没想出来，看了评论区的答案分享我才知道自己走错了路，思想刚开始是对的，的确要搞一个 dp[i]，但是在遍历时是对每个面值都要进行比较，选出最小的那种方案才对。这个答案还是很好理解的，只是我思考的方向不对，进入了思维的盲区。

Solution

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (coins.empty()) return -1;
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i)
            for (int j = 0; j < coins.size(); ++j)
                if (coins[j] <= i)
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
        return dp[amount] <= amount ? dp[amount] : -1;
    }
};